{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Langtons Ant LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: printKMoves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #兰顿蚂蚁"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。</p>\n",
    "\n",
    "<p>(1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。<br>\n",
    "(2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。</p>\n",
    "\n",
    "<p>编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。</p>\n",
    "\n",
    "<p>网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由&nbsp;<code>&#39;X&#39;</code>&nbsp;表示，白色方格由&nbsp;<code>&#39;_&#39;</code>&nbsp;表示，蚂蚁所在的位置由&nbsp;<code>&#39;L&#39;</code>, <code>&#39;U&#39;</code>, <code>&#39;R&#39;</code>, <code>&#39;D&#39;</code>&nbsp;表示，分别表示蚂蚁&nbsp;左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> 0\n",
    "<strong>输出: </strong>[&quot;R&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> 2\n",
    "<strong>输出:\n",
    "</strong>[\n",
    "&nbsp; &quot;_X&quot;,\n",
    "&nbsp; &quot;LX&quot;\n",
    "]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> 5\n",
    "<strong>输出:\n",
    "</strong>[\n",
    "&nbsp; &quot;_U&quot;,\n",
    "&nbsp; &quot;X_&quot;,\n",
    "&nbsp; &quot;XX&quot;\n",
    "]\n",
    "</pre>\n",
    "\n",
    "<p><strong>说明：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>K &lt;= 100000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [langtons-ant-lcci](https://leetcode.cn/problems/langtons-ant-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [langtons-ant-lcci](https://leetcode.cn/problems/langtons-ant-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef printKMoves(self, k):\n",
    "\t\tdiff = [[0,1], [1,0], [0,-1], [-1,0]]\n",
    "\t\tant = ['R','D','L','U']\n",
    "\t\td = 0\n",
    "\t\tborder = [0,0,0,0]\n",
    "\t\tblack = set()\n",
    "\t\tx = 0\n",
    "\t\ty = 0\n",
    "\t\tfor _ in range(k):\n",
    "\t\t\tif (x, y) in black:\n",
    "\t\t\t\td = (d - 1) % 4\n",
    "\t\t\t\tblack.remove((x, y))\n",
    "\t\t\t\tx += diff[d][0]\n",
    "\t\t\t\ty += diff[d][1]\n",
    "\t\t\t\tself.update(border, x, y)\n",
    "\t\t\telse:\n",
    "\t\t\t\td = (d + 1) % 4\n",
    "\t\t\t\tblack.add((x, y))\n",
    "\t\t\t\tx += diff[d][0]\n",
    "\t\t\t\ty += diff[d][1]\n",
    "\t\t\t\tself.update(border, x, y)\n",
    "\t\tans = []\n",
    "\t\tfor i in range(border[0], border[2] + 1):\n",
    "\t\t\trow = ['X' if (i, j) in black else '_' for j in range(border[1], border[3] + 1)]\n",
    "\t\t\tif i == x:\n",
    "\t\t\t\trow[y - border[1]] = ant[d]\n",
    "\t\t\tans.append(''.join(row))\n",
    "\t\treturn ans\n",
    "\t\n",
    "\tdef update(self, arr, x, y):\n",
    "\t\tarr[0] = min(arr[0], x)\n",
    "\t\tarr[1] = min(arr[1], y)\n",
    "\t\tarr[2] = max(arr[2], x)\n",
    "\t\tarr[3] = max(arr[3], y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        # 定义状态 和方向\n",
    "        state, direction = 0, [(0, 1, 'R'), (1, 0, 'D'), (0, -1, 'L'), (-1, 0, 'U')]\n",
    "        net = dict()\n",
    "        # 记录当前位置，和最小 最大坐标\n",
    "        pos, min_, max_ = (0, 0), (0, 0), (0, 0)\n",
    "        \n",
    "        for _ in range(K):\n",
    "            if net.get(pos, '_') == '_':\n",
    "                net[pos] = 'X'\n",
    "                # 顺时针\n",
    "                state = (state + 1) % 4  \n",
    "            else:\n",
    "                net[pos] = '_'\n",
    "                # 逆时针\n",
    "                state = (state - 1) % 4\n",
    "            # 向前移动\n",
    "            pos = (pos[0] + direction[state][0], pos[1] + direction[state][1])\n",
    "            # 记录两边界坐标\n",
    "            min_ = (min(min_[0], pos[0]), min(min_[1], pos[1]))\n",
    "            max_ = (max(max_[0], pos[0]), max(max_[1], pos[1]))\n",
    "        net[pos] = direction[state][2]\n",
    "\n",
    "        ans = [''.join([net.get((i, j), '_') for j in range(min_[1], max_[1] + 1)]) \n",
    "                for i in range(min_[0], max_[0] + 1)]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        colors = {(0, 0): 0}\n",
    "        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        d, x, y = 0, 0, 0\n",
    "        for _ in range(K):\n",
    "            if colors[(x, y)] == 1:\n",
    "                d = (d + 3) % 4\n",
    "            else:\n",
    "                d = (d + 1) % 4\n",
    "            colors[(x, y)] = 1 - colors[(x, y)]\n",
    "            x, y = x + dirs[d][0], y + dirs[d][1]\n",
    "            if (x, y) not in colors:\n",
    "                colors[(x, y)] = 0\n",
    "        min_x, min_y = 1000000, 1000000\n",
    "        max_x, max_y = -1000000, -1000000\n",
    "        for tx, ty in colors.keys():\n",
    "            min_x = min(min_x, tx)\n",
    "            max_x = max(max_x, tx)\n",
    "            min_y = min(min_y, ty)\n",
    "            max_y = max(max_y, ty)\n",
    "        facing = [\"R\", \"D\", \"L\", \"U\"]\n",
    "        board = [\"\" for _ in range(max_x - min_x + 1)]\n",
    "        for i in range(min_x, max_x + 1):\n",
    "            for j in range(min_y, max_y + 1):\n",
    "                if i == x and j == y:\n",
    "                    board[i - min_x] += facing[d]\n",
    "                elif (i, j) in colors and colors[(i, j)] == 1:\n",
    "                    board[i - min_x] += \"X\"\n",
    "                else:\n",
    "                    board[i - min_x] += \"_\"\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "         # 定义状态 和方向\n",
    "        state, direction = 0, [(0, 1, 'R'), (1, 0, 'D'), (0, -1, 'L'), (-1, 0, 'U')]\n",
    "        net = dict()\n",
    "        # 记录当前位置，和最小 最大坐标\n",
    "        pos, min_, max_ = (0, 0), (0, 0), (0, 0)\n",
    "\n",
    "        for _ in range(K):\n",
    "            if net.get(pos, '_') == '_':\n",
    "                net[pos] = 'X'\n",
    "                # 顺时针\n",
    "                state = (state + 1) % 4\n",
    "            else:\n",
    "                net[pos] = '_'\n",
    "                # 逆时针\n",
    "                state = (state - 1) % 4\n",
    "            # 向前移动\n",
    "            pos = (pos[0] + direction[state][0], pos[1] + direction[state][1])\n",
    "            # 记录两边界坐标\n",
    "            min_ = (min(min_[0], pos[0]), min(min_[1], pos[1]))\n",
    "            max_ = (max(max_[0], pos[0]), max(max_[1], pos[1]))\n",
    "        net[pos] = direction[state][2]\n",
    "\n",
    "        ans = [''.join([net.get((i, j), '_') for j in range(min_[1], max_[1] + 1)])\n",
    "            for i in range(min_[0], max_[0] + 1)]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dirs = {(0, -1):\"L\", (-1, 0):\"U\", (0, 1):\"R\", (1, 0):\"D\"}\n",
    "clockwise = [0, 1, -1, 0]\n",
    "counterwise = [0, -1, 1, 0]\n",
    "class Ant:\n",
    "    def __init__(self, x=0, y=0, dx=0, dy=1):\n",
    "        self.location = (x, y)\n",
    "        self.direction = (dx, dy)\n",
    "\n",
    "    def turn(self, turn):\n",
    "        dx, dy = self.direction\n",
    "        self.direction = (dx * turn[0] + dy * turn[1], dx * turn[2] + dy * turn[3])\n",
    "\n",
    "    def step(self):\n",
    "        self.location = (self.location[0] + self.direction[0], self.location[1] + self.direction[1])\n",
    "\n",
    "    def get_direction(self):\n",
    "        return dirs.get(self.direction)\n",
    "    \n",
    "    def get_location(self):\n",
    "        return self.location\n",
    "\n",
    "class Board:\n",
    "    def __init__(self, white, black):\n",
    "        self.white = white\n",
    "        self.black = black\n",
    "        self.board = dict()\n",
    "        self.top = 0\n",
    "        self.bottom = 0\n",
    "        self.left = 0\n",
    "        self.right = 0\n",
    "        self.set_color(0, 0, white)\n",
    "\n",
    "    def get_color(self, x, y):\n",
    "        # 注意设置默认值，如果之前没有到达过的均设置为白色\n",
    "        return self.board.get((x, y), self.white)\n",
    "    \n",
    "    def set_color(self, x, y, color):\n",
    "        self.board[(x, y)] = color \n",
    "        self.top = min(self.top, x)                 # 更新上边界\n",
    "        self.bottom = max(self.bottom, x)           # 更新下边界\n",
    "        self.left = min(self.left, y)               # 更新左边界\n",
    "        self.right = max(self.right, y)\n",
    "\n",
    "    def change_color(self, x, y):\n",
    "        color = self.get_color(x, y)\n",
    "        if color == self.white:\n",
    "            self.set_color(x, y, self.black)\n",
    "        else:\n",
    "            self.set_color(x, y, self.white)\n",
    "\n",
    "    def get_board(self, ant):\n",
    "        direciton = ant.get_direction()\n",
    "        x, y = ant.location\n",
    "        cur_color = self.get_color(x, y)\n",
    "        self.set_color(x, y, direciton)\n",
    "        ans = []\n",
    "        for i in range(self.top, self.bottom+1):\n",
    "            line = []\n",
    "            for j in range(self.left, self.right + 1):\n",
    "                line.append(self.get_color(i, j))\n",
    "            ans.append(\"\".join(line))\n",
    "        # self.set_color(x, y, cur_color)  # 考虑到封闭性，可以把颜色改回来\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        ant = Ant(0, 0, 0, 1)\n",
    "        white = \"_\"\n",
    "        black = \"X\"\n",
    "        board = Board(white, black)\n",
    "        for _ in range(K):\n",
    "            x, y = ant.location\n",
    "            color = board.get_color(x, y)\n",
    "            if color == white:\n",
    "                ant.turn(clockwise)\n",
    "            else:\n",
    "                ant.turn(counterwise)\n",
    "            board.change_color(x, y)        # 当前块改变颜色\n",
    "            ant.step()                      # 蚂蚁前进一步\n",
    "        return board.get_board(ant)\n",
    "\n",
    "        \n",
    "\n",
    "        # 由于matrix是一个边界一直在变化的矩阵, 考虑使用一个dict记录，比数组更好\n",
    "        # def nextMoves(x, y, cur_color, matrix):\n",
    "        #     m, n = len(matrix), len(matrix[0])\n",
    "        #     dx, dy = dirs[matrix[x][y]]\n",
    "        #     if 0 <= x + dx < m and 0 <= y + dy < n:\n",
    "        #         if cur_color == \"_\"\n",
    "        #             matrix[x][y] = \n",
    "                \n",
    "        #         cur_color = matrix[x+dx][y+dy]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        # 方向：0 - 左，1 - 上，2 - 右，3 - 下\n",
    "        direction = 2\n",
    "        # 蚂蚁的初始位置\n",
    "        x, y = 0, 0\n",
    "        # 记录网格的状态：白色或黑色\n",
    "        grid = {(x, y): '_'}\n",
    "        # 记录边界\n",
    "        min_x, min_y, max_x, max_y = 0, 0, 0, 0\n",
    "\n",
    "        # 用于表示方向的增量\n",
    "        dx = [0, -1, 0, 1]\n",
    "        dy = [-1, 0, 1, 0]\n",
    "\n",
    "        for _ in range(K):\n",
    "            # 根据蚂蚁当前所在方格的颜色来改变方向\n",
    "            if grid.get((x, y), '_') == '_':\n",
    "                direction = (direction + 1) % 4\n",
    "                grid[(x, y)] = 'X'\n",
    "            else:\n",
    "                direction = (direction - 1) % 4\n",
    "                grid[(x, y)] = '_'\n",
    "            \n",
    "            # 更新蚂蚁的位置\n",
    "            x += dx[direction]\n",
    "            y += dy[direction]\n",
    "            # 更新边界\n",
    "            min_x, min_y, max_x, max_y = min(min_x, x), min(min_y, y), max(max_x, x), max(max_y, y)\n",
    "            # 默认设置为白色（如果尚未设置）\n",
    "            grid.setdefault((x, y), '_')\n",
    "\n",
    "        # 在最后一步，标记蚂蚁的位置和方向\n",
    "        grid[(x, y)] = 'LURD'[direction]\n",
    "\n",
    "        # 构造最终的网格数组\n",
    "        result = []\n",
    "        for i in range(min_x, max_x + 1):\n",
    "            row = []\n",
    "            for j in range(min_y, max_y + 1):\n",
    "                row.append(grid.get((i, j), '_'))\n",
    "            result.append(\"\".join(row))\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "\n",
    "        white, black = \"_\", \"X\"                     # 白色用“_”表示，黑色用“X”表示\n",
    "        ant = Ant()                                 # 实例化一只蚂蚁\n",
    "        board = Board(white=white, black=black)     # 实例化一个网格\n",
    "        for _ in range(K):                          # 重复K次\n",
    "            color = board.get_color(ant.location)   # 获取网格中蚂蚁所在位置处的颜色\n",
    "            if color == white:                      # 如果是白色\n",
    "                ant.turn_right()                    # 蚂蚁需要右转\n",
    "            elif color == black:                    # 如果是黑色\n",
    "                ant.turn_left()                     # 蚂蚁需要左转\n",
    "            else:                                   # 非法颜色\n",
    "                raise Exception(color)              # 提示报错\n",
    "            board.change_color(ant.location)        # 翻转蚂蚁所在位置颜色\n",
    "            ant.step()                              # 蚂蚁向前一步走\n",
    "        board.set_color(ant.location, ant.current_direction)    # 最后，要把蚂蚁所在位置处的颜色设置成蚂蚁的当前方向\n",
    "        ans = board.get_ans                         # 根据网格中记录的蚂蚁足迹获取最终结果\n",
    "        return ans                                  # 返回结果\n",
    "\n",
    "\n",
    "class Ant:                                          # 定义一只蚂蚁\n",
    "    def __init__(self):                             # 蚂蚁的初始化\n",
    "        self.location = (0, 0)                      # 位置属性：初始化为原点\n",
    "        self.direction = (0, 1)                     # 方向属性：初始化为向右\n",
    "\n",
    "    @staticmethod\n",
    "    def matmul(vector, mat):                        # 实现向量乘以矩阵，因为向量乘以矩阵可以实现旋转\n",
    "        dh, dw = vector\n",
    "        [[a, b], [c, d]] = mat\n",
    "        return dh * a + dw * c, dh * b + dw * d\n",
    "\n",
    "    def turn_left(self):                            # 当前方向左转，需要将当前方向乘以左转矩阵\n",
    "        self.direction = self.matmul(self.direction, [[0, 1], [-1, 0]])\n",
    "\n",
    "    def turn_right(self):                           # 当前方向右转，需要将当前方向乘以右转矩阵\n",
    "        self.direction = self.matmul(self.direction, [[0, -1], [1, 0]])\n",
    "\n",
    "    def step(self):                                 # 基于当前的方向，向前一步走\n",
    "        self.location = (self.location[0] + self.direction[0], self.location[1] + self.direction[1])\n",
    "\n",
    "    @property\n",
    "    def current_direction(self):                    # 获取当前方向的字母表示\n",
    "        d = {(0, 1): \"R\",                           # 右\n",
    "             (0, -1): \"L\",                          # 左\n",
    "             (1, 0): \"D\",                           # 下\n",
    "             (-1, 0): \"U\",                          # 上\n",
    "             }\n",
    "        return d[self.direction]                    # 索引查找\n",
    "\n",
    "\n",
    "class Board:                                        # 定义一个网格\n",
    "    def __init__(self, white=\"_\", black=\"X\"):       # 网格的初始化函数\n",
    "        self.footprint = dict()                     # 蚂蚁在网格上留下的足迹，即每个位置点及其对应的颜色，默认颜色是白色\n",
    "        self.white = white                          # 白色默认用“_”表示\n",
    "        self.black = black                          # 黑色默认用“X”表示\n",
    "        self.top = 0                                # 网格的上边界\n",
    "        self.left = 0                               # 网格的左边界\n",
    "        self.bottom = 0                             # 网格的下边界\n",
    "        self.right = 0                              # 网格的右边界\n",
    "\n",
    "    def get_color(self, pos):                       # 获取某个位置处网格颜色，默认颜色为白色\n",
    "        return self.footprint.get(pos, self.white)\n",
    "\n",
    "    def set_color(self, pos, color):                # 设置网格某个位置pos处颜色为color\n",
    "        self.footprint[pos] = color\n",
    "        self.update_border(pos)                     # 每次设置pos处颜色，需要根据pos更新一下边界\n",
    "\n",
    "    def change_color(self, pos):                    # 翻转网格的颜色\n",
    "        color = self.get_color(pos)                 # 当前颜色，非黑即白，否则报错\n",
    "        if color == self.white:                     # 如果当前位置pos处颜色是白色\n",
    "            self.set_color(pos, self.black)         # 设置当前位置pos处颜色为黑色\n",
    "        elif color == self.black:                   # 如果当前位置pos处颜色为黑色\n",
    "            self.set_color(pos, self.white)         # 设置当前位置pos处颜色为白色\n",
    "        else:                                       # 如果是其他颜色\n",
    "            raise Exception(color)                  # 则会报错\n",
    "\n",
    "    def update_border(self, pos):                   # 更新网格边界\n",
    "        h, w = pos                                  # pos处的h和w坐标\n",
    "        self.top = min(self.top, h)                 # 更新上边界\n",
    "        self.bottom = max(self.bottom, h)           # 更新下边界\n",
    "        self.left = min(self.left, w)               # 更新左边界\n",
    "        self.right = max(self.right, w)             # 更新右边界\n",
    "\n",
    "    @property\n",
    "    def get_ans(self):                              # 根据足迹获取结果\n",
    "        ans = []                                    # 结果列表\n",
    "        for h in range(self.top, self.bottom + 1):  # 逐行研究\n",
    "            line = \"\"                               # 当前行结果\n",
    "            for w in range(self.left, self.right + 1):              # 逐列研究\n",
    "                line += self.get_color((h, w))      # 获取当前位置(h, w)结果\n",
    "            ans.append(line)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dirs = {(0, -1):\"L\", (-1, 0):\"U\", (0, 1):\"R\", (1, 0):\"D\"}\n",
    "clockwise = [0, 1, -1, 0]\n",
    "counterwise = [0, -1, 1, 0]\n",
    "class Ant:\n",
    "    def __init__(self, x=0, y=0, dx=0, dy=1):\n",
    "        self.location = (x, y)\n",
    "        self.direction = (dx, dy)\n",
    "\n",
    "    def turn(self, turn):\n",
    "        dx, dy = self.direction\n",
    "        self.direction = (dx * turn[0] + dy * turn[1], dx * turn[2] + dy * turn[3])\n",
    "\n",
    "    def step(self):\n",
    "        self.location = (self.location[0] + self.direction[0], self.location[1] + self.direction[1])\n",
    "\n",
    "    def get_direction(self):\n",
    "        return dirs.get(self.direction)\n",
    "    \n",
    "    def get_location(self):\n",
    "        return self.location\n",
    "\n",
    "class Board:\n",
    "    def __init__(self, white, black):\n",
    "        self.white = white\n",
    "        self.black = black\n",
    "        self.board = dict()\n",
    "        self.top = 0\n",
    "        self.bottom = 0\n",
    "        self.left = 0\n",
    "        self.right = 0\n",
    "        self.set_color(0, 0, white)\n",
    "\n",
    "    def get_color(self, x, y):\n",
    "        # 注意设置默认值，如果之前没有到达过的均设置为白色\n",
    "        return self.board.get((x, y), self.white)\n",
    "    \n",
    "    def set_color(self, x, y, color):\n",
    "        self.board[(x, y)] = color \n",
    "        self.top = min(self.top, x)                 # 更新上边界\n",
    "        self.bottom = max(self.bottom, x)           # 更新下边界\n",
    "        self.left = min(self.left, y)               # 更新左边界\n",
    "        self.right = max(self.right, y)\n",
    "\n",
    "    def change_color(self, x, y):\n",
    "        color = self.get_color(x, y)\n",
    "        if color == self.white:\n",
    "            self.set_color(x, y, self.black)\n",
    "        else:\n",
    "            self.set_color(x, y, self.white)\n",
    "\n",
    "    def get_board(self, ant):\n",
    "        direciton = ant.get_direction()\n",
    "        x, y = ant.location\n",
    "        cur_color = self.get_color(x, y)\n",
    "        self.set_color(x, y, direciton)\n",
    "        ans = []\n",
    "        for i in range(self.top, self.bottom+1):\n",
    "            line = []\n",
    "            for j in range(self.left, self.right + 1):\n",
    "                line.append(self.get_color(i, j))\n",
    "            ans.append(\"\".join(line))\n",
    "        # self.set_color(x, y, cur_color)  # 考虑到封闭性，可以把颜色改回来\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        ant = Ant(0, 0, 0, 1)\n",
    "        white = \"_\"\n",
    "        black = \"X\"\n",
    "        board = Board(white, black)\n",
    "        for _ in range(K):\n",
    "            x, y = ant.location\n",
    "            color = board.get_color(x, y)\n",
    "            if color == white:\n",
    "                ant.turn(clockwise)\n",
    "            else:\n",
    "                ant.turn(counterwise)\n",
    "            board.change_color(x, y)        # 当前块改变颜色\n",
    "            ant.step()                      # 蚂蚁前进一步\n",
    "        return board.get_board(ant)\n",
    "\n",
    "        \n",
    "\n",
    "        # 由于matrix是一个边界一直在变化的矩阵, 考虑使用一个dict记录，比数组更好\n",
    "        # def nextMoves(x, y, cur_color, matrix):\n",
    "        #     m, n = len(matrix), len(matrix[0])\n",
    "        #     dx, dy = dirs[matrix[x][y]]\n",
    "        #     if 0 <= x + dx < m and 0 <= y + dy < n:\n",
    "        #         if cur_color == \"_\"\n",
    "        #             matrix[x][y] = \n",
    "                \n",
    "        #         cur_color = matrix[x+dx][y+dy]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "\n",
    "\n",
    "\n",
    "        white, black = \"_\", \"X\"                     # 白色用“_”表示，黑色用“X”表示\n",
    "\n",
    "        ant = Ant()                                 # 实例化一只蚂蚁\n",
    "\n",
    "        board = Board(white=white, black=black)     # 实例化一个网格\n",
    "\n",
    "        for _ in range(K):                          # 重复K次\n",
    "\n",
    "            color = board.get_color(ant.location)   # 获取网格中蚂蚁所在位置处的颜色\n",
    "\n",
    "            if color == white:                      # 如果是白色\n",
    "\n",
    "                ant.turn_right()                    # 蚂蚁需要右转\n",
    "\n",
    "            elif color == black:                    # 如果是黑色\n",
    "\n",
    "                ant.turn_left()                     # 蚂蚁需要左转\n",
    "\n",
    "            else:                                   # 非法颜色\n",
    "\n",
    "                raise Exception(color)              # 提示报错\n",
    "\n",
    "            board.change_color(ant.location)        # 翻转蚂蚁所在位置颜色\n",
    "\n",
    "            ant.step()                              # 蚂蚁向前一步走\n",
    "\n",
    "        board.set_color(ant.location, ant.current_direction)    # 最后，要把蚂蚁所在位置处的颜色设置成蚂蚁的当前方向\n",
    "\n",
    "        ans = board.get_ans                         # 根据网格中记录的蚂蚁足迹获取最终结果\n",
    "\n",
    "        return ans                                  # 返回结果\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Ant:                                          # 定义一只蚂蚁\n",
    "\n",
    "    def __init__(self):                             # 蚂蚁的初始化\n",
    "\n",
    "        self.location = (0, 0)                      # 位置属性：初始化为原点\n",
    "\n",
    "        self.direction = (0, 1)                     # 方向属性：初始化为向右\n",
    "\n",
    "\n",
    "\n",
    "    @staticmethod\n",
    "\n",
    "    def matmul(vector, mat):                        # 实现向量乘以矩阵，因为向量乘以矩阵可以实现旋转\n",
    "\n",
    "        dh, dw = vector\n",
    "\n",
    "        [[a, b], [c, d]] = mat\n",
    "\n",
    "        return dh * a + dw * c, dh * b + dw * d\n",
    "\n",
    "\n",
    "\n",
    "    def turn_left(self):                            # 当前方向左转，需要将当前方向乘以左转矩阵\n",
    "\n",
    "        self.direction = self.matmul(self.direction, [[0, 1], [-1, 0]])\n",
    "\n",
    "\n",
    "\n",
    "    def turn_right(self):                           # 当前方向右转，需要将当前方向乘以右转矩阵\n",
    "\n",
    "        self.direction = self.matmul(self.direction, [[0, -1], [1, 0]])\n",
    "\n",
    "\n",
    "\n",
    "    def step(self):                                 # 基于当前的方向，向前一步走\n",
    "\n",
    "        self.location = (self.location[0] + self.direction[0], self.location[1] + self.direction[1])\n",
    "\n",
    "\n",
    "\n",
    "    @property\n",
    "\n",
    "    def current_direction(self):                    # 获取当前方向的字母表示\n",
    "\n",
    "        d = {(0, 1): \"R\",                           # 右\n",
    "\n",
    "             (0, -1): \"L\",                          # 左\n",
    "\n",
    "             (1, 0): \"D\",                           # 下\n",
    "\n",
    "             (-1, 0): \"U\",                          # 上\n",
    "\n",
    "             }\n",
    "\n",
    "        return d[self.direction]                    # 索引查找\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Board:                                        # 定义一个网格\n",
    "\n",
    "    def __init__(self, white=\"_\", black=\"X\"):       # 网格的初始化函数\n",
    "\n",
    "        self.footprint = dict()                     # 蚂蚁在网格上留下的足迹，即每个位置点及其对应的颜色，默认颜色是白色\n",
    "\n",
    "        self.white = white                          # 白色默认用“_”表示\n",
    "\n",
    "        self.black = black                          # 黑色默认用“X”表示\n",
    "\n",
    "        self.top = 0                                # 网格的上边界\n",
    "\n",
    "        self.left = 0                               # 网格的左边界\n",
    "\n",
    "        self.bottom = 0                             # 网格的下边界\n",
    "\n",
    "        self.right = 0                              # 网格的右边界\n",
    "\n",
    "\n",
    "\n",
    "    def get_color(self, pos):                       # 获取某个位置处网格颜色，默认颜色为白色\n",
    "\n",
    "        return self.footprint.get(pos, self.white)\n",
    "\n",
    "\n",
    "\n",
    "    def set_color(self, pos, color):                # 设置网格某个位置pos处颜色为color\n",
    "\n",
    "        self.footprint[pos] = color\n",
    "\n",
    "        self.update_border(pos)                     # 每次设置pos处颜色，需要根据pos更新一下边界\n",
    "\n",
    "\n",
    "\n",
    "    def change_color(self, pos):                    # 翻转网格的颜色\n",
    "\n",
    "        color = self.get_color(pos)                 # 当前颜色，非黑即白，否则报错\n",
    "\n",
    "        if color == self.white:                     # 如果当前位置pos处颜色是白色\n",
    "\n",
    "            self.set_color(pos, self.black)         # 设置当前位置pos处颜色为黑色\n",
    "\n",
    "        elif color == self.black:                   # 如果当前位置pos处颜色为黑色\n",
    "\n",
    "            self.set_color(pos, self.white)         # 设置当前位置pos处颜色为白色\n",
    "\n",
    "        else:                                       # 如果是其他颜色\n",
    "\n",
    "            raise Exception(color)                  # 则会报错\n",
    "\n",
    "\n",
    "\n",
    "    def update_border(self, pos):                   # 更新网格边界\n",
    "\n",
    "        h, w = pos                                  # pos处的h和w坐标\n",
    "\n",
    "        self.top = min(self.top, h)                 # 更新上边界\n",
    "\n",
    "        self.bottom = max(self.bottom, h)           # 更新下边界\n",
    "\n",
    "        self.left = min(self.left, w)               # 更新左边界\n",
    "\n",
    "        self.right = max(self.right, w)             # 更新右边界\n",
    "\n",
    "\n",
    "\n",
    "    @property\n",
    "\n",
    "    def get_ans(self):                              # 根据足迹获取结果\n",
    "\n",
    "        ans = []                                    # 结果列表\n",
    "\n",
    "        for h in range(self.top, self.bottom + 1):  # 逐行研究\n",
    "\n",
    "            line = \"\"                               # 当前行结果\n",
    "\n",
    "            for w in range(self.left, self.right + 1):              # 逐列研究\n",
    "\n",
    "                line += self.get_color((h, w))      # 获取当前位置(h, w)结果\n",
    "\n",
    "            ans.append(line)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "s = Solution()\n",
    "\n",
    "for i in range(6):\n",
    "\n",
    "    print()\n",
    "\n",
    "    print(\"\\n\".join(s.printKMoves(i)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "         # 定义状态 和方向\n",
    "        state, direction = 0, [(0, 1, 'R'), (1, 0, 'D'), (0, -1, 'L'), (-1, 0, 'U')]\n",
    "        net = dict()\n",
    "        # 记录当前位置，和最小 最大坐标\n",
    "        pos, min_, max_ = (0, 0), (0, 0), (0, 0)\n",
    "\n",
    "        for _ in range(K):\n",
    "            if net.get(pos, '_') == '_':\n",
    "                net[pos] = 'X'\n",
    "                # 顺时针\n",
    "                state = (state + 1) % 4\n",
    "            else:\n",
    "                net[pos] = '_'\n",
    "                # 逆时针\n",
    "                state = (state - 1) % 4\n",
    "            # 向前移动\n",
    "            pos = (pos[0] + direction[state][0], pos[1] + direction[state][1])\n",
    "            # 记录两边界坐标\n",
    "            min_ = (min(min_[0], pos[0]), min(min_[1], pos[1]))\n",
    "            max_ = (max(max_[0], pos[0]), max(max_[1], pos[1]))\n",
    "        net[pos] = direction[state][2]\n",
    "\n",
    "        ans = [''.join([net.get((i, j), '_') for j in range(min_[1], max_[1] + 1)])\n",
    "            for i in range(min_[0], max_[0] + 1)]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        state, direction = 0, [(0, 1, 'R'), (1, 0, 'D'), (0, -1, 'L'), (-1, 0, 'U')]\n",
    "        pos, min_, max_ = (0, 0), (0, 0), (0, 0)\n",
    "        net = dict()\n",
    "        for _ in range(K):\n",
    "            if net.get(pos, '_') == '_':\n",
    "                net[pos] = 'X'\n",
    "                state = (state + 1) % 4\n",
    "            else:\n",
    "                net[pos] =  '_'\n",
    "                state = (state - 1) % 4\n",
    "            pos = (pos[0] + direction [state][0], pos[1] + direction [state][1])\n",
    "            min_ = (min(min_[0], pos[0]), min(min_[1], pos[1]))\n",
    "            max_ = (max(max_[0], pos[0]), max(max_[1], pos[1]))\n",
    "        net[pos] = direction [state][2]\n",
    "        return [''.join([net.get((i, j), '_') for j in range(min_[1], max_[1] + 1)])\n",
    "                for i in range(min_[0], max_[0] + 1)]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        # 定义状态 和方向\n",
    "        state, direction = 0, [(0, 1, 'R'), (1, 0, 'D'), (0, -1, 'L'), (-1, 0, 'U')]\n",
    "        net = dict()\n",
    "        # 记录当前位置，和最小 最大坐标\n",
    "        pos, min_, max_ = (0, 0), (0, 0), (0, 0)\n",
    "        \n",
    "        for _ in range(K):\n",
    "            if net.get(pos, '_') == '_':\n",
    "                net[pos] = 'X'\n",
    "                # 顺时针\n",
    "                state = (state + 1) % 4  \n",
    "            else:\n",
    "                net[pos] = '_'\n",
    "                # 逆时针\n",
    "                state = (state - 1) % 4\n",
    "            # 向前移动\n",
    "            pos = (pos[0] + direction[state][0], pos[1] + direction[state][1])\n",
    "            # 记录两边界坐标\n",
    "            min_ = (min(min_[0], pos[0]), min(min_[1], pos[1]))\n",
    "            max_ = (max(max_[0], pos[0]), max(max_[1], pos[1]))\n",
    "        net[pos] = direction[state][2]\n",
    "\n",
    "        ans = [''.join([net.get((i, j), '_') for j in range(min_[1], max_[1] + 1)]) \n",
    "                for i in range(min_[0], max_[0] + 1)]\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        if K==0:return ['R']\n",
    "        if K==1:return ['X','D']\n",
    "        diffs = {'D':(1,0),'L':(0,-1),'U':(-1,0),'R':(0,1)}\n",
    "        dirct = ['R','D','L','U']\n",
    "        ans = ['-'*(K+1)]*(K+1) if K<128 else ['-'*(K//20+1)]*(K//20+1)\n",
    "        x,y,z = len(ans)//2,len(ans)//2,0\n",
    "        for i in range(1,K+1):\n",
    "            # print(x,y,ans[x])\n",
    "            if ans[x][y]=='_' or ans[x][y]=='-':\n",
    "                z = (z+1)%4\n",
    "                ans[x] = ans[x][:y]+'X'+ans[x][y+1:]\n",
    "            else:\n",
    "                z = (z-1)%4\n",
    "                ans[x] = ans[x][:y]+'_'+ans[x][y+1:]\n",
    "            x += diffs[dirct[z]][0]\n",
    "            y += diffs[dirct[z]][1]\n",
    "        # print(x,y,z)\n",
    "        ans[x] = ans[x][:y]+dirct[z]+ans[x][y+1:]\n",
    "        # print(len(ans))\n",
    "        l,r= K+1,0\n",
    "        acc,re = {},[]\n",
    "        for i in range(len(ans)):\n",
    "            if len(set(ans[i]))==1 and ans[i][0]=='-':continue\n",
    "            tmp,li,ri,num = '',K+1,0,''\n",
    "            begin,end = len(ans)-len(ans[i].lstrip('-')),len(ans[i].rstrip('-'))\n",
    "            for j in range(begin,end+1):\n",
    "                if ans[i][j]!='-':\n",
    "                    li,ri = min(li,j),max(ri,j)\n",
    "                    tmp += num+ans[i][j]\n",
    "                    num = ''\n",
    "                else:\n",
    "                    num+='_'\n",
    "            l,r = min(l,li),max(r,ri)\n",
    "            if tmp:\n",
    "                acc[(tmp,i)] = (li,ri)\n",
    "                re.append((tmp,i))\n",
    "        # print(len(re))\n",
    "        res = []\n",
    "        for c in re:\n",
    "            # print(acc[c],l,r)\n",
    "            res.append(c[0].ljust(r-acc[c][0]+1,'_').rjust(r-l+1,'_'))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        if K==0:return ['R']\n",
    "        if K==1:return ['X','D']\n",
    "        diffs = {'D':(1,0),'L':(0,-1),'U':(-1,0),'R':(0,1)}\n",
    "        dirct = ['R','D','L','U']\n",
    "        ans = ['-'*(K+1)]*(K+1) if K<128 else ['-'*(K//16+1)]*(K//16+1)\n",
    "        x,y,z = len(ans)//2,len(ans)//2,0\n",
    "        for i in range(1,K+1):\n",
    "            # print(x,y,ans[x])\n",
    "            if ans[x][y]=='_' or ans[x][y]=='-':\n",
    "                z = (z+1)%4\n",
    "                ans[x] = ans[x][:y]+'X'+ans[x][y+1:]\n",
    "            else:\n",
    "                z = (z-1)%4\n",
    "                ans[x] = ans[x][:y]+'_'+ans[x][y+1:]\n",
    "            x += diffs[dirct[z]][0]\n",
    "            y += diffs[dirct[z]][1]\n",
    "        # print(x,y,z)\n",
    "        ans[x] = ans[x][:y]+dirct[z]+ans[x][y+1:]\n",
    "        # print(len(ans))\n",
    "        l,r= K+1,0\n",
    "        acc,re = {},[]\n",
    "        for i in range(len(ans)):\n",
    "            if len(set(ans[i]))==1 and ans[i][0]=='-':continue\n",
    "            tmp,li,ri,num = '',K+1,0,''\n",
    "            begin,end = len(ans)-len(ans[i].lstrip('-')),len(ans[i].rstrip('-'))\n",
    "            for j in range(begin,end+1):\n",
    "                if ans[i][j]!='-':\n",
    "                    li,ri = min(li,j),max(ri,j)\n",
    "                    tmp += num+ans[i][j]\n",
    "                    num = ''\n",
    "                else:\n",
    "                    num+='_'\n",
    "            l,r = min(l,li),max(r,ri)\n",
    "            if tmp:\n",
    "                acc[(tmp,i)] = (li,ri)\n",
    "                re.append((tmp,i))\n",
    "        print(len(re))\n",
    "        res = []\n",
    "        for c in re:\n",
    "            # print(acc[c],l,r)\n",
    "            res.append(c[0].ljust(r-acc[c][0]+1,'_').rjust(r-l+1,'_'))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        if K==0:return ['R']\n",
    "        if K==1:return ['X','D']\n",
    "        diffs = {'D':(1,0),'L':(0,-1),'U':(-1,0),'R':(0,1)}\n",
    "        dirct = ['R','D','L','U']\n",
    "        ans = ['-'*(K+1)]*(K+1) if K<128 else ['-'*(K//16+1)]*(K//16+1)\n",
    "        x,y,z = len(ans)//2,len(ans)//2,0\n",
    "        for i in range(1,K+1):\n",
    "            # print(x,y,ans[x])\n",
    "            if ans[x][y]=='_' or ans[x][y]=='-':\n",
    "                z = (z+1)%4\n",
    "                ans[x] = ans[x][:y]+'X'+ans[x][y+1:]\n",
    "            else:\n",
    "                z = (z-1)%4\n",
    "                ans[x] = ans[x][:y]+'_'+ans[x][y+1:]\n",
    "            x += diffs[dirct[z]][0]\n",
    "            y += diffs[dirct[z]][1]\n",
    "        # print(x,y,z)\n",
    "        ans[x] = ans[x][:y]+dirct[z]+ans[x][y+1:]\n",
    "        # print(len(ans))\n",
    "        l,r= K+1,0\n",
    "        acc,re = {},[]\n",
    "        for i in range(len(ans)):\n",
    "            if len(set(ans[i]))==1 and ans[i][0]=='-':continue\n",
    "            tmp,li,ri,num = '',K+1,0,''\n",
    "            begin,end = len(ans)-len(ans[i].lstrip('-')),len(ans[i].rstrip('-'))\n",
    "            for j in range(begin,end+1):\n",
    "                if ans[i][j]!='-':\n",
    "                    li,ri = min(li,j),max(ri,j)\n",
    "                    tmp += num+ans[i][j]\n",
    "                    num = ''\n",
    "                else:\n",
    "                    num+='_'\n",
    "            l,r = min(l,li),max(r,ri)\n",
    "            if tmp:\n",
    "                acc[(tmp,i)] = (li,ri)\n",
    "                re.append((tmp,i))\n",
    "        # print(len(re))\n",
    "        res = []\n",
    "        for c in re:\n",
    "            # print(acc[c],l,r)\n",
    "            res.append(c[0].ljust(r-acc[c][0]+1,'_').rjust(r-l+1,'_'))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        if K==0:return ['R']\n",
    "        if K==1:return ['X','D']\n",
    "        diffs = {'D':(1,0),'L':(0,-1),'U':(-1,0),'R':(0,1)}\n",
    "        dirct = ['R','D','L','U']\n",
    "        ans = ['-'*(K+1)]*(K+1) if K<128 else ['-'*(K//8+1)]*(K//8+1)\n",
    "        x,y,z = len(ans)//2,len(ans)//2,0\n",
    "        for i in range(1,K+1):\n",
    "            # print(x,y,ans[x])\n",
    "            if ans[x][y]=='_' or ans[x][y]=='-':\n",
    "                z = (z+1)%4\n",
    "                ans[x] = ans[x][:y]+'X'+ans[x][y+1:]\n",
    "            else:\n",
    "                z = (z-1)%4\n",
    "                ans[x] = ans[x][:y]+'_'+ans[x][y+1:]\n",
    "            x += diffs[dirct[z]][0]\n",
    "            y += diffs[dirct[z]][1]\n",
    "        # print(x,y,z)\n",
    "        ans[x] = ans[x][:y]+dirct[z]+ans[x][y+1:]\n",
    "        # print(ans[K//2-2])\n",
    "        l,r= K+1,0\n",
    "        acc,re = {},[]\n",
    "        for i in range(len(ans)):\n",
    "            if len(set(ans[i]))==1 and ans[i][0]=='-':continue\n",
    "            tmp,li,ri,num = '',K+1,0,''\n",
    "            begin,end = len(ans)-len(ans[i].lstrip('-')),len(ans[i].rstrip('-'))\n",
    "            for j in range(begin,end+1):\n",
    "                if ans[i][j]!='-':\n",
    "                    li,ri = min(li,j),max(ri,j)\n",
    "                    tmp += num+ans[i][j]\n",
    "                    num = ''\n",
    "                else:\n",
    "                    num+='_'\n",
    "            l,r = min(l,li),max(r,ri)\n",
    "            if tmp:\n",
    "                acc[(tmp,i)] = (li,ri)\n",
    "                re.append((tmp,i))\n",
    "        # print(acc,re,l,r)\n",
    "        res = []\n",
    "        for c in re:\n",
    "            # print(acc[c],l,r)\n",
    "            res.append(c[0].ljust(r-acc[c][0]+1,'_').rjust(r-l+1,'_'))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "\n",
    "        Map=defaultdict(dict)\n",
    "\n",
    "        x,y,maxX,maxY,minX,minY=0,0,0,0,0,0\n",
    "\n",
    "        pos,p=['L','U','R','D'],2   #p=2表示蚂蚁方向朝右\n",
    "\n",
    "        move=[[0,-1],[-1,0],[0,1],[1,0]]\n",
    "\n",
    "        Map[0][0]='_'\n",
    "\n",
    "        for _ in range(K):\n",
    "\n",
    "            if y in Map[x] and Map[x][y]=='X':\n",
    "\n",
    "                Map[x][y]='_'\n",
    "\n",
    "                p=(p-1)%4   #-1表示左旋转\n",
    "\n",
    "            else:       #如果xy不在哈西表中，或是它在且值为_，就说明这个位置是白色\n",
    "\n",
    "                Map[x][y]='X'\n",
    "\n",
    "                p=(p+1)%4   #+1表示右旋转\n",
    "\n",
    "            x,y=x+move[p][0],y+move[p][1]   #旋转后，根据朝向进行移动\n",
    "\n",
    "            \n",
    "\n",
    "            if x>maxX:  #此处用于修正蚂蚁移动到的最大范围\n",
    "\n",
    "                maxX=x\n",
    "\n",
    "            elif x<minX:\n",
    "\n",
    "                minX=x\n",
    "\n",
    "            if y>maxY:\n",
    "\n",
    "                maxY=y\n",
    "\n",
    "            elif y<minY:\n",
    "\n",
    "                minY=y\n",
    "\n",
    "\n",
    "\n",
    "        ans=[['_']*(maxY-minY+1) for _ in range(maxX-minX+1)]\n",
    "\n",
    "        for X in Map:\n",
    "\n",
    "            for Y in Map[X]:\n",
    "\n",
    "                ans[X-minX][Y-minY]=Map[X][Y]   #由于我们把minX,minY重置为坐标零点，所以需要添加这个偏移量\n",
    "\n",
    "        ans[x-minX][y-minY]=pos[p]              #最后标记蚂蚁最终朝向\n",
    "\n",
    "        for i in range(maxX-minX+1):\n",
    "\n",
    "            ans[i]=''.join(ans[i])              #把单字符串成字符串\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        Map=defaultdict(dict)\n",
    "        x,y,maxX,maxY,minX,minY=0,0,0,0,0,0\n",
    "        pos,p=['L','U','R','D'],2   #p=2表示蚂蚁方向朝右\n",
    "        move=[[0,-1],[-1,0],[0,1],[1,0]]\n",
    "        Map[0][0]='_'\n",
    "        for _ in range(K):\n",
    "            if y in Map[x] and Map[x][y]=='X':\n",
    "                Map[x][y]='_'\n",
    "                p=(p-1)%4   #-1表示左旋转\n",
    "            else:       #如果xy不在哈西表中，或是它在且值为_，就说明这个位置是白色\n",
    "                Map[x][y]='X'\n",
    "                p=(p+1)%4   #+1表示右旋转\n",
    "            x,y=x+move[p][0],y+move[p][1]   #旋转后，根据朝向进行移动\n",
    "            \n",
    "            if x>maxX:  #此处用于修正蚂蚁移动到的最大范围\n",
    "                maxX=x\n",
    "            elif x<minX:\n",
    "                minX=x\n",
    "            if y>maxY:\n",
    "                maxY=y\n",
    "            elif y<minY:\n",
    "                minY=y\n",
    "\n",
    "        ans=[['_']*(maxY-minY+1) for _ in range(maxX-minX+1)]\n",
    "        for X in Map:\n",
    "            for Y in Map[X]:\n",
    "                ans[X-minX][Y-minY]=Map[X][Y]   #由于我们把minX,minY重置为坐标零点，所以需要添加这个偏移量\n",
    "        ans[x-minX][y-minY]=pos[p]              #最后标记蚂蚁最终朝向\n",
    "        for i in range(maxX-minX+1):\n",
    "            ans[i]=''.join(ans[i])              #把单字符串成字符串\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        Map=defaultdict(dict)\n",
    "        x,y,maxX,maxY,minX,minY=0,0,0,0,0,0\n",
    "        pos,p=['L','U','R','D'],2   #p=2表示蚂蚁方向朝右\n",
    "        move=[[0,-1],[-1,0],[0,1],[1,0]]\n",
    "        Map[0][0]='_'\n",
    "        for _ in range(K):\n",
    "            if y in Map[x] and Map[x][y]=='X':\n",
    "                Map[x][y]='_'\n",
    "                p=(p-1)%4   #-1表示左旋转\n",
    "            else:       #如果xy不在哈西表中，或是它在且值为_，就说明这个位置是白色\n",
    "                Map[x][y]='X'\n",
    "                p=(p+1)%4   #+1表示右旋转\n",
    "            x,y=x+move[p][0],y+move[p][1]   #旋转后，根据朝向进行移动\n",
    "            \n",
    "            if x>maxX:  #此处用于修正蚂蚁移动到的最大范围\n",
    "                maxX=x\n",
    "            elif x<minX:\n",
    "                minX=x\n",
    "            if y>maxY:\n",
    "                maxY=y\n",
    "            elif y<minY:\n",
    "                minY=y\n",
    "\n",
    "        ans=[['_']*(maxY-minY+1) for _ in range(maxX-minX+1)]\n",
    "        for X in Map:\n",
    "            for Y in Map[X]:\n",
    "                ans[X-minX][Y-minY]=Map[X][Y]   #由于我们把minX,minY重置为坐标零点，所以需要添加这个偏移量\n",
    "        ans[x-minX][y-minY]=pos[p]              #最后标记蚂蚁最终朝向\n",
    "        for i in range(maxX-minX+1):\n",
    "            ans[i]=''.join(ans[i])              #把单字符串成字符串\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        Map=defaultdict(dict)\n",
    "        x,y,maxX,maxY,minX,minY=0,0,0,0,0,0\n",
    "        pos,p=['L','U','R','D'],2   #p=2表示蚂蚁方向朝右\n",
    "        move=[[0,-1],[-1,0],[0,1],[1,0]]\n",
    "        Map[0][0]='_'\n",
    "        for _ in range(K):\n",
    "            if y in Map[x] and Map[x][y]=='X':\n",
    "                Map[x][y]='_'\n",
    "                p=(p-1)%4   #-1表示左旋转\n",
    "            else:       #如果xy不在哈西表中，或是它在且值为_，就说明这个位置是白色\n",
    "                Map[x][y]='X'\n",
    "                p=(p+1)%4   #+1表示右旋转\n",
    "            x,y=x+move[p][0],y+move[p][1]   #旋转后，根据朝向进行移动\n",
    "            \n",
    "            if x>maxX:  #此处用于修正蚂蚁移动到的最大范围\n",
    "                maxX=x\n",
    "            elif x<minX:\n",
    "                minX=x\n",
    "            if y>maxY:\n",
    "                maxY=y\n",
    "            elif y<minY:\n",
    "                minY=y\n",
    "\n",
    "        ans=[['_']*(maxY-minY+1) for _ in range(maxX-minX+1)]\n",
    "        for X in Map:\n",
    "            for Y in Map[X]:\n",
    "                ans[X-minX][Y-minY]=Map[X][Y]   #由于我们把minX,minY重置为坐标零点，所以需要添加这个偏移量\n",
    "        ans[x-minX][y-minY]=pos[p]              #最后标记蚂蚁最终朝向\n",
    "        for i in range(maxX-minX+1):\n",
    "            ans[i]=''.join(ans[i])              #把单字符串成字符串\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        grid = defaultdict(dict)\n",
    "        x, y, maxX, maxY, minX, minY = 0, 0, 0, 0, 0, 0\n",
    "        pos, p = ['L','U','R','D'], 2   #p=2表示蚂蚁方向朝右\n",
    "        move=[[0, -1], [-1, 0], [0, 1], [1, 0]]\n",
    "        grid[0][0] = '_'\n",
    "        for _ in range(K):\n",
    "            if y in grid[x] and grid[x][y] == 'X':\n",
    "                grid[x][y] = '_'\n",
    "                p = (p - 1) % 4   #-1表示左旋转\n",
    "            else:       #如果xy不在哈西表中，或是它在且值为_，就说明这个位置是白色\n",
    "                grid[x][y] = 'X'\n",
    "                p = (p + 1) % 4   #+1表示右旋转\n",
    "            x, y = x + move[p][0], y + move[p][1]   #旋转后，根据朝向进行移动\n",
    "            \n",
    "            if x > maxX:  #此处用于修正蚂蚁移动到的最大范围\n",
    "                maxX = x\n",
    "            elif x < minX:\n",
    "                minX = x\n",
    "            if y > maxY:\n",
    "                maxY = y\n",
    "            elif y < minY:\n",
    "                minY = y\n",
    "\n",
    "        ans = [['_'] * (maxY - minY + 1) for _ in range(maxX - minX + 1)]\n",
    "        for X in grid:\n",
    "            for Y in grid[X]:\n",
    "                ans[X - minX][Y - minY] = grid[X][Y]   #由于我们把minX,minY重置为坐标零点，所以需要添加这个偏移量\n",
    "        ans[x - minX][y - minY] = pos[p]              #最后标记蚂蚁最终朝向\n",
    "        for i in range(maxX - minX + 1):\n",
    "            ans[i] = ''.join(ans[i])              #把单字符串成字符串\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        black = set()\n",
    "        d = [(1, 0), (0, -1), (-1, 0), (0, 1)]\n",
    "        faces = {0: 'R', 1: 'D', 2: 'L', 3: 'U'}\n",
    "        maxx, maxy, minx, miny = 0, 0, 0, 0\n",
    "        face = 0\n",
    "        x, y = 0, 0\n",
    "        for _ in range(K):\n",
    "            if (x, y) in black:\n",
    "                face = (face-1)%4\n",
    "                black.remove((x, y))\n",
    "            else:\n",
    "                face = (face+1)%4\n",
    "                black.add((x, y))\n",
    "            x, y = x + d[face][0], y + d[face][1]\n",
    "            maxx = max(maxx, x)\n",
    "            maxy = max(maxy, y)\n",
    "            minx = min(minx, x)\n",
    "            miny = min(miny, y)\n",
    "        n, m = max(1, maxx - minx+1), max(1, maxy - miny+1)\n",
    "        res = [['_' for _ in range(n)] for _ in range(m)]\n",
    "        for i, j in black:\n",
    "            res[m-1-j+miny][i-minx] = 'X'\n",
    "        res[m-1-y+miny][x-minx] = faces[face]\n",
    "        for i in range(m):\n",
    "            res[i] = ''.join(res[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        board = defaultdict()\n",
    "        \n",
    "        xmax = 0\n",
    "        xmin = 0\n",
    "        ymax = 0\n",
    "        ymin = 0\n",
    "        mov = [\n",
    "            [0, -1], \n",
    "            [-1, 0],\n",
    "            [0, 1],\n",
    "            [1, 0]\n",
    "        ]\n",
    "        \n",
    "        d = 2 \n",
    "        xcur, ycur = 0, 0\n",
    "        board[(xcur, ycur)] = '_'\n",
    "\n",
    "        for _ in range(K):\n",
    "            if (xcur,ycur) in board.keys() and board[(xcur, ycur)] == 'X':\n",
    "                board[(xcur, ycur)] = '_'  \n",
    "                d = (d-1) % 4\n",
    "            else:\n",
    "                board[(xcur, ycur)] = 'X'\n",
    "                d = (d+1) % 4\n",
    "            \n",
    "            xcur += mov[d][0]\n",
    "            ycur += mov[d][1]\n",
    "            \n",
    "            xmax = xcur if xcur>xmax else xmax \n",
    "            xmin = xcur if xcur<xmin else xmin \n",
    "            ymax = ycur if ycur>ymax else ymax \n",
    "            ymin = ycur if ycur<ymin else ymin \n",
    "\n",
    "        res = [['_']*(ymax-ymin+1) for _ in range(xmax-xmin+1)]\n",
    "        for (x,y) in board.keys():\n",
    "            res[x-xmin][y-ymin] = board[(x, y)]\n",
    "        \n",
    "        dirs = ['L', 'U', 'R', 'D']\n",
    "        res[xcur-xmin][ycur-ymin] = dirs[d]\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            res[i] = ''.join(res[i])\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        board = defaultdict()\n",
    "        \n",
    "        xmax = 0\n",
    "        xmin = 0\n",
    "        ymax = 0\n",
    "        ymin = 0\n",
    "        mov = [\n",
    "            [0, -1], \n",
    "            [-1, 0],\n",
    "            [0, 1],\n",
    "            [1, 0]\n",
    "        ]\n",
    "        \n",
    "        d = 2 \n",
    "        xcur, ycur = 0, 0\n",
    "        board[(xcur, ycur)] = '_'\n",
    "\n",
    "        for _ in range(K):\n",
    "            if (xcur,ycur) in board.keys():\n",
    "                if board[(xcur, ycur)] == 'X':\n",
    "                    board[(xcur, ycur)] = '_'  \n",
    "                    d = (d-1) % 4\n",
    "                else:\n",
    "                    board[(xcur, ycur)] = 'X'\n",
    "                    d = (d+1) % 4\n",
    "            else:\n",
    "                board[(xcur, ycur)] = 'X'\n",
    "                d = (d+1) % 4\n",
    "            \n",
    "            xcur += mov[d][0]\n",
    "            ycur += mov[d][1]\n",
    "            \n",
    "            xmax = xcur if xcur>xmax else xmax \n",
    "            xmin = xcur if xcur<xmin else xmin \n",
    "            ymax = ycur if ycur>ymax else ymax \n",
    "            ymin = ycur if ycur<ymin else ymin \n",
    "\n",
    "        res = [['_']*(ymax-ymin+1) for _ in range(xmax-xmin+1)]\n",
    "        for (x,y) in board.keys():\n",
    "            res[x-xmin][y-ymin] = board[(x, y)]\n",
    "        \n",
    "        dirs = ['L', 'U', 'R', 'D']\n",
    "        res[xcur-xmin][ycur-ymin] = dirs[d]\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            res[i] = ''.join(res[i])\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        board = defaultdict()\n",
    "        \n",
    "        xmax = 0\n",
    "        xmin = 0\n",
    "        ymax = 0\n",
    "        ymin = 0\n",
    "        mov = [\n",
    "            [0, -1], \n",
    "            [-1, 0],\n",
    "            [0, 1],\n",
    "            [1, 0]\n",
    "        ]\n",
    "        \n",
    "        d = 2 \n",
    "        xcur, ycur = 0, 0\n",
    "        board[(xcur, ycur)] = '_'\n",
    "\n",
    "        for _ in range(K):\n",
    "            if (xcur,ycur) in board.keys():\n",
    "                if board[(xcur, ycur)] == 'X':\n",
    "                    board[(xcur, ycur)] = '_'  \n",
    "                    d = (d-1) % 4\n",
    "                else:\n",
    "                    board[(xcur, ycur)] = 'X'\n",
    "                    d = (d+1) % 4\n",
    "            else:\n",
    "                board[(xcur, ycur)] = 'X'\n",
    "                d = (d+1) % 4\n",
    "            \n",
    "            xcur += mov[d][0]\n",
    "            ycur += mov[d][1]\n",
    "            \n",
    "            xmax = xcur if xcur>xmax else xmax \n",
    "            xmin = xcur if xcur<xmin else xmin \n",
    "            ymax = ycur if ycur>ymax else ymax \n",
    "            ymin = ycur if ycur<ymin else ymin \n",
    "\n",
    "        res = [['_']*(ymax-ymin+1) for _ in range(xmax-xmin+1)]\n",
    "        for (x,y) in board.keys():\n",
    "            res[x-xmin][y-ymin] = board[(x, y)]\n",
    "        \n",
    "        dirs = ['L', 'U', 'R', 'D']\n",
    "        res[xcur-xmin][ycur-ymin] = dirs[d]\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            res[i] = ''.join(res[i])\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        board = defaultdict()\n",
    "        \n",
    "        xmax = 0\n",
    "        xmin = 0\n",
    "        ymax = 0\n",
    "        ymin = 0\n",
    "        mov = [\n",
    "            [0, -1], \n",
    "            [-1, 0],\n",
    "            [0, 1],\n",
    "            [1, 0]\n",
    "        ]\n",
    "        \n",
    "        d = 2 \n",
    "        xcur, ycur = 0, 0\n",
    "        board[(xcur, ycur)] = '_'\n",
    "\n",
    "        for _ in range(K):\n",
    "            if (xcur,ycur) in board.keys():\n",
    "                if board[(xcur, ycur)] == 'X':\n",
    "                    board[(xcur, ycur)] = '_'  \n",
    "                    d = (d-1) % 4\n",
    "                else:\n",
    "                    board[(xcur, ycur)] = 'X'\n",
    "                    d = (d+1) % 4\n",
    "            else:\n",
    "                board[(xcur, ycur)] = 'X'\n",
    "                d = (d+1) % 4\n",
    "            \n",
    "            xcur += mov[d][0]\n",
    "            ycur += mov[d][1]\n",
    "            \n",
    "            xmax = xcur if xcur>xmax else xmax \n",
    "            xmin = xcur if xcur<xmin else xmin \n",
    "            ymax = ycur if ycur>ymax else ymax \n",
    "            ymin = ycur if ycur<ymin else ymin \n",
    "\n",
    "        res = [['_']*(ymax-ymin+1) for _ in range(xmax-xmin+1)]\n",
    "        for (x,y) in board.keys():\n",
    "            res[x-xmin][y-ymin] = board[(x, y)]\n",
    "        \n",
    "        dirs = ['L', 'U', 'R', 'D']\n",
    "        res[xcur-xmin][ycur-ymin] = dirs[d]\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            res[i] = ''.join(res[i])\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        board = defaultdict()\n",
    "        \n",
    "        xmax = 0\n",
    "        xmin = 0\n",
    "        ymax = 0\n",
    "        ymin = 0\n",
    "        mov = [\n",
    "            [0, -1], \n",
    "            [-1, 0],\n",
    "            [0, 1],\n",
    "            [1, 0]\n",
    "        ]\n",
    "        \n",
    "        d = 2 \n",
    "        xcur, ycur = 0, 0\n",
    "        board[(xcur, ycur)] = '_'\n",
    "\n",
    "        for _ in range(K):\n",
    "            if (xcur,ycur) in board.keys():\n",
    "                if board[(xcur, ycur)] == 'X':\n",
    "                    board[(xcur, ycur)] = '_'  \n",
    "                    d = (d-1) % 4\n",
    "                else:\n",
    "                    board[(xcur, ycur)] = 'X'\n",
    "                    d = (d+1) % 4\n",
    "            else:\n",
    "                board[(xcur, ycur)] = 'X'\n",
    "                d = (d+1) % 4\n",
    "            \n",
    "            xcur += mov[d][0]\n",
    "            ycur += mov[d][1]\n",
    "            \n",
    "            xmax = xcur if xcur>xmax else xmax \n",
    "            xmin = xcur if xcur<xmin else xmin \n",
    "            ymax = ycur if ycur>ymax else ymax \n",
    "            ymin = ycur if ycur<ymin else ymin \n",
    "\n",
    "        res = [['_']*(ymax-ymin+1) for _ in range(xmax-xmin+1)]\n",
    "        for (x,y) in board.keys():\n",
    "            res[x-xmin][y-ymin] = board[(x, y)]\n",
    "        \n",
    "        dirs = ['L', 'U', 'R', 'D']\n",
    "        res[xcur-xmin][ycur-ymin] = dirs[d]\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            res[i] = ''.join(res[i])\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        board = defaultdict()\n",
    "        \n",
    "        xmax = 0\n",
    "        xmin = 0\n",
    "        ymax = 0\n",
    "        ymin = 0\n",
    "        mov = [\n",
    "            [0, -1], \n",
    "            [-1, 0],\n",
    "            [0, 1],\n",
    "            [1, 0]\n",
    "        ]\n",
    "        \n",
    "        d = 2 \n",
    "        xcur, ycur = 0, 0\n",
    "        board[(xcur, ycur)] = '_'\n",
    "\n",
    "        for _ in range(K):\n",
    "            if (xcur,ycur) in board:\n",
    "                if board[(xcur, ycur)] == 'X':\n",
    "                    board[(xcur, ycur)] = '_'  \n",
    "                    d = (d-1) % 4\n",
    "                else:\n",
    "                    board[(xcur, ycur)] = 'X'\n",
    "                    d = (d+1) % 4\n",
    "            else:\n",
    "                board[(xcur, ycur)] = 'X'\n",
    "                d = (d+1) % 4\n",
    "            \n",
    "            xcur += mov[d][0]\n",
    "            ycur += mov[d][1]\n",
    "            \n",
    "            xmax = xcur if xcur>xmax else xmax \n",
    "            xmin = xcur if xcur<xmin else xmin \n",
    "            ymax = ycur if ycur>ymax else ymax \n",
    "            ymin = ycur if ycur<ymin else ymin \n",
    "\n",
    "        res = [['_']*(ymax-ymin+1) for _ in range(xmax-xmin+1)]\n",
    "        for (x,y) in board.keys():\n",
    "            res[x-xmin][y-ymin] = board[(x, y)]\n",
    "        \n",
    "        dirs = ['L', 'U', 'R', 'D']\n",
    "        res[xcur-xmin][ycur-ymin] = dirs[d]\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            res[i] = ''.join(res[i])\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        black = set()\n",
    "        d = [(1, 0), (0, -1), (-1, 0), (0, 1)]\n",
    "        faces = {0: 'R', 1: 'D', 2: 'L', 3: 'U'}\n",
    "        maxx, maxy, minx, miny = 0, 0, 0, 0\n",
    "        face = 0\n",
    "        x, y = 0, 0\n",
    "        for _ in range(K):\n",
    "            if (x, y) in black:\n",
    "                face = (face-1)%4\n",
    "                black.remove((x, y))\n",
    "            else:\n",
    "                face = (face+1)%4\n",
    "                black.add((x, y))\n",
    "            x, y = x + d[face][0], y + d[face][1]\n",
    "            maxx = max(maxx, x)\n",
    "            maxy = max(maxy, y)\n",
    "            minx = min(minx, x)\n",
    "            miny = min(miny, y)\n",
    "        n, m = max(1, maxx - minx+1), max(1, maxy - miny+1)\n",
    "        res = [['_' for _ in range(n)] for _ in range(m)]\n",
    "        for i, j in black:\n",
    "            res[j-miny][i-minx] = 'X'\n",
    "        res[y-miny][x-minx] = faces[face]\n",
    "        res = res[::-1]\n",
    "        for i in range(m):\n",
    "            res[i] = ''.join(res[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        dir=['R','D','L','U']\n",
    "        curx,cury,curd=0,0,0\n",
    "        minx,maxx,miny,maxy=0,0,0,0\n",
    "        dc={(0,0):0}\n",
    "        for _ in range(K):\n",
    "            pos=(curx,cury)\n",
    "            color=0 if not pos in dc else dc[pos]\n",
    "            if color==0:\n",
    "                curd=(curd+1)%4\n",
    "            else:\n",
    "                curd=(curd-1)%4\n",
    "            dc[pos]=1-color\n",
    "            if curd==0:\n",
    "                curx+=1\n",
    "                maxx=max(maxx,curx)\n",
    "            elif curd==1:\n",
    "                cury+=1\n",
    "                maxy=max(maxy,cury)\n",
    "            elif curd==2:\n",
    "                curx-=1\n",
    "                minx=min(minx,curx)\n",
    "            else:\n",
    "                cury-=1\n",
    "                miny=min(miny,cury)\n",
    "        n,m=maxx-minx+1,maxy-miny+1\n",
    "        matrix=[[\"_\"]*n for _ in range(m)]\n",
    "        for x,y in dc:\n",
    "            matrix[y-miny][x-minx]=\"_\" if dc[(x,y)]==0 else \"X\"\n",
    "        matrix[cury-miny][curx-minx]=dir[curd]\n",
    "        res=[]\n",
    "        for i in range(m):\n",
    "            res.append(''.join(matrix[i]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        blackSet = set()\n",
    "        D = (0, 1), (1, 0), (0, -1), (-1, 0)\n",
    "        idx = 0\n",
    "        minX, minY, maxX, maxY = inf, inf, -inf, -inf\n",
    "        antX = antY = 0\n",
    "        for i in range(K):\n",
    "            if (antX, antY) in blackSet:\n",
    "                blackSet.remove((antX, antY))\n",
    "                idx = (idx - 1) % 4\n",
    "            else:\n",
    "                blackSet.add((antX, antY))\n",
    "                idx = (idx + 1) % 4\n",
    "            \n",
    "            minX = min(minX, antX)\n",
    "            minY = min(minY, antY)\n",
    "            maxX = max(maxX, antX)\n",
    "            maxY = max(maxY, antY)\n",
    "            antX += D[idx][0]\n",
    "            antY += D[idx][1]\n",
    "        \n",
    "        minX = min(minX, antX)\n",
    "        minY = min(minY, antY)\n",
    "        maxX = max(maxX, antX)\n",
    "        maxY = max(maxY, antY)\n",
    "        ans = [['_' for i in range(maxY - minY + 1)] for j in range(maxX - minX + 1)]\n",
    "        for i, j in blackSet:\n",
    "            ans[i - minX][j - minY] = 'X'\n",
    "    \n",
    "        ans[antX - minX][antY - minY] = 'RDLU'[idx]\n",
    "\n",
    "        return list(map(lambda x: ''.join(x), ans))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        diffs = {'D':(1,0),'L':(0,-1),'U':(-1,0),'R':(0,1)}\n",
    "        dirct = ['R','D','L','U']\n",
    "        ans = {}\n",
    "        xmin,xmax,ymin,ymax = 0,0,0,0\n",
    "        x,y,z = 0,0,0\n",
    "        for i in range(K):\n",
    "            if (x,y) not in ans:ans[(x,y)] = '_'\n",
    "            if ans[(x,y)]=='_':\n",
    "                z = (z+1)%4\n",
    "                ans[(x,y)] = 'X'\n",
    "            else:\n",
    "                z = (z-1)%4\n",
    "                ans[(x,y)] = '_'\n",
    "            x += diffs[dirct[z]][0]\n",
    "            y += diffs[dirct[z]][1]\n",
    "            xmin,xmax = min(x,xmin),max(x,xmax)\n",
    "            ymin,ymax = min(y,ymin),max(y,ymax)\n",
    "        ans[(x,y)] = dirct[z]\n",
    "        res = [['_']*(ymax-ymin+1) for i in range(xmax-xmin+1)]\n",
    "        for (x,y),v in ans.items():\n",
    "            res[x-xmin][y-ymin] = v\n",
    "        return [''.join(c) for c in res]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        diffs = {'D':(1,0),'L':(0,-1),'U':(-1,0),'R':(0,1)}\n",
    "        dirct = ['R','D','L','U']\n",
    "        ans = {}\n",
    "        xmin,xmax,ymin,ymax = 0,0,0,0\n",
    "        x,y,z = 0,0,0\n",
    "        for i in range(K):\n",
    "            if (x,y) not in ans:ans[(x,y)] = '_'\n",
    "            if ans[(x,y)]=='_':\n",
    "                z = (z+1)%4\n",
    "                ans[(x,y)] = 'X'\n",
    "            else:\n",
    "                z = (z-1)%4\n",
    "                ans[(x,y)] = '_'\n",
    "            x += diffs[dirct[z]][0]\n",
    "            y += diffs[dirct[z]][1]\n",
    "            xmin,xmax = min(x,xmin),max(x,xmax)\n",
    "            ymin,ymax = min(y,ymin),max(y,ymax)\n",
    "        ans[(x,y)] = dirct[z]\n",
    "        res = [['_']*(ymax-ymin+1) for i in range(xmax-xmin+1)]\n",
    "        for (x,y),v in ans.items():\n",
    "            res[x-xmin][y-ymin] = v\n",
    "        return [''.join(c) for c in res]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        diffs = {'D':(1,0),'L':(0,-1),'U':(-1,0),'R':(0,1)}\n",
    "        dirct = ['R','D','L','U']\n",
    "        ans = {}\n",
    "        xmin,xmax,ymin,ymax = 0,0,0,0\n",
    "        x,y,z = 0,0,0\n",
    "        for i in range(K):\n",
    "            if (x,y) not in ans:ans[(x,y)] = '_'\n",
    "            if ans[(x,y)]=='_':\n",
    "                z = (z+1)%4\n",
    "                ans[(x,y)] = 'X'\n",
    "            else:\n",
    "                z = (z-1)%4\n",
    "                ans[(x,y)] = '_'\n",
    "            x += diffs[dirct[z]][0]\n",
    "            y += diffs[dirct[z]][1]\n",
    "            xmin,xmax = min(x,xmin),max(x,xmax)\n",
    "            ymin,ymax = min(y,ymin),max(y,ymax)\n",
    "        ans[(x,y)] = dirct[z]\n",
    "        res = [['_']*(ymax-ymin+1) for i in range(xmax-xmin+1)]\n",
    "        for (x,y),v in ans.items():\n",
    "            res[x-xmin][y-ymin] = v\n",
    "        return [''.join(c) for c in res]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        ds = ['R', 'D', 'L', 'U']\n",
    "        ps = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        gridd = {(0,0):'_'}\n",
    "\n",
    "        x0, y0 = 0, 0\n",
    "        x1, y1 = 1, 1\n",
    "\n",
    "        x, y = 0, 0\n",
    "        idx = 0\n",
    "\n",
    "        for _ in range(K):\n",
    "            # 翻转当前格子\n",
    "            if gridd.get((x,y), '_') == '_':\n",
    "                gridd[(x,y)] = 'X'\n",
    "                u = 1\n",
    "            else:\n",
    "                gridd[(x,y)] = '_'\n",
    "                u = -1\n",
    "            \n",
    "            # 旋转\n",
    "            idx = (idx + u) % 4\n",
    "\n",
    "            dx, dy = ps[idx]\n",
    "\n",
    "            # 更新位置\n",
    "            x += dx\n",
    "            y += dy\n",
    "\n",
    "            if x < x0:\n",
    "                x0 = x\n",
    "            if y < y0:\n",
    "                y0 = y\n",
    "            if x == x1:\n",
    "                x1 += 1\n",
    "            elif y == y1:\n",
    "                y1 += 1\n",
    "\n",
    "        grid = [['_']*(y1-y0) for _ in range(x1-x0)]\n",
    "        for (xi, yi), v in gridd.items():\n",
    "            grid[xi-x0][yi-y0] = v\n",
    "\n",
    "        # 插入当前位置\n",
    "        grid[x-x0][y-y0] = ds[idx]\n",
    "\n",
    "        return [''.join(row) for row in grid]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        record = {}\n",
    "        x, y, minx, miny, maxx, maxy = 0, 0, 0, 0, 0, 0\n",
    "        record[(x, y)] = '_'\n",
    "        pos = ['L', 'U', 'R', 'D']\n",
    "        direction = [[0, -1], [-1, 0], [0, 1], [1, 0]]\n",
    "        p = 2\n",
    "        for _  in range(K):\n",
    "            if (x, y) in record and record[(x, y)] == 'X':\n",
    "                record[(x, y)] = '_'\n",
    "                p = (p-1)%4\n",
    "            else:\n",
    "                record[(x, y)] = 'X'\n",
    "                p = (p+1)%4\n",
    "\n",
    "            x, y = x+direction[p][0], y+direction[p][1]\n",
    "\n",
    "            if x > maxx:\n",
    "                maxx = x\n",
    "            if x < minx:\n",
    "                minx = x\n",
    "            if y > maxy:\n",
    "                maxy = y\n",
    "            if y < miny:\n",
    "                miny = y\n",
    "        \n",
    "        res = [['_' for _ in range(maxy-miny+1)] for _ in range(maxx-minx+1)]\n",
    "        ans = []\n",
    "        for (i, j) in record:\n",
    "            res[i-minx][j-miny] = record[(i, j)]\n",
    "        res[x-minx][y-miny] = pos[p]\n",
    "        for i in range(maxx-minx+1):\n",
    "            ans.append(''.join(res[i]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        res = []\n",
    "        dir = [\"R\", \"D\", \"L\", \"U\"]\n",
    "        move = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        self.curDir = 0\n",
    "        r = 0\n",
    "        c = 0\n",
    "        data = {}\n",
    "        minR = 0\n",
    "        minC = 0\n",
    "        maxR = 0\n",
    "        maxC = 0\n",
    "\n",
    "        def fill(r, c, offset, color):\n",
    "            data[(r, c)] = color\n",
    "            self.curDir += offset\n",
    "            if self.curDir < 0:\n",
    "                self.curDir = 3\n",
    "            elif self.curDir > 3:\n",
    "                self.curDir = 0\n",
    "            r += move[self.curDir][0]\n",
    "            c += move[self.curDir][1]\n",
    "            return r, c\n",
    "\n",
    "        while K:\n",
    "            if (r, c) not in data:\n",
    "                r, c = fill(r, c, 1, \"X\")\n",
    "            else:\n",
    "                if data[(r, c)] == \"_\":\n",
    "                    r, c = fill(r, c, 1, \"X\")\n",
    "                else:\n",
    "                    r, c = fill(r, c, -1, \"_\")\n",
    "            minC = min(minC, c)\n",
    "            minR = min(minR, r)\n",
    "            maxC = max(maxC, c)\n",
    "            maxR = max(maxR, r)\n",
    "            K -= 1\n",
    "\n",
    "        height = maxR + abs(minR) + 1\n",
    "        width = maxC + abs(minC) + 1\n",
    "        data[(r, c)] = dir[self.curDir]\n",
    "        for i in range(height):\n",
    "            res.append([\"_\" for _ in range(width)])\n",
    "        for (r, c) in data:\n",
    "            res[r+abs(minR)][c+abs(minC)] = data[(r, c)]\n",
    "\n",
    "        final_res = []\n",
    "        for d in res:\n",
    "            final_res.append(\"\".join(d))\n",
    "        return final_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        \n",
    "        # 本题重点，没有预期多大的矩阵，需要用path记录走过的点坐标，并且记录最值边界，最后再用边界生成矩阵\n",
    "        path = defaultdict(str)\n",
    "\n",
    "        min_x, min_y, max_x, max_y = 0,0,0,0 # 边界: x是行边界，y是列边界\n",
    "\n",
    "        face = ['L','U','R','D'] # 朝向查找集合\n",
    "        move = [[0,-1],[-1,0],[0,1],[1,0]] # 移动数组，[r, c] 分别表示行移动和列移动向量，并且位置i与face对应，比如'L'表示左转，位置是行不变。列负方向移动一位\n",
    "\n",
    "        x,y,p = 0,0,2 # 初始位置和face数组idx\n",
    "        path[(x,y)] = '_' # 初始路径\n",
    "\n",
    "        for i in range(K):\n",
    "            if (x,y) in path and path[(x,y)] == 'X': # （x,y）是走过的点，且之前的值是‘X’\n",
    "                path[(x,y)] = '_' # 按题意转换颜色\n",
    "                p = (p-1)%4 # 按题意，需要逆时针旋转，即face数组反着移动一位\n",
    "\n",
    "            else: # (x,y)没走过，或者之前的值是‘_’\n",
    "                path[(x,y)] = 'X' # 按题意转换颜色\n",
    "                p = (p+1)%4 # 按题意，需要顺时针旋转，即face数组正向着移动一位\n",
    "                        \n",
    "            x,y = x + move[p][0], y + move[p][1] # 根据朝向，移动到新的位置上\n",
    "\n",
    "            # 每走一步，都比较记录边界\n",
    "            min_x = min(min_x, x)\n",
    "            min_y = min(min_y, y)\n",
    "            max_x = max(max_x, x)\n",
    "            max_y = max(max_y, y)\n",
    "\n",
    "        # 根据边界，初始化一个固定大小的矩阵\n",
    "        board = [['_' for _ in range(max_y-min_y+1)] for _ in range(max_x-min_x+1)]\n",
    "\n",
    "        for (i,j), mark in path.items():\n",
    "            board[i-min_x][j-min_y] = mark # 把（min_x, min_y）设置为坐标零点，进行坐标变化并设置矩阵格里面的值\n",
    "\n",
    "        board[x-min_x][y-min_y] = face[p] # x,y 是最终的位置，坐标变换后，设置蚂蚁的朝向\n",
    "\n",
    "        res = [''.join(row) for row in board]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        \n",
    "        # 本题重点，没有预期多大的矩阵，需要用map记录走过的point，并且记录边界，最后再用边界生成矩阵\n",
    "\n",
    "        path = defaultdict(str)\n",
    "\n",
    "        min_x, min_y, max_x, max_y = 0,0,0,0 # 边界: x是行边界，y是列边界\n",
    "\n",
    "        face = ['L','U','R','D'] # 朝向查找集合\n",
    "        move = [[0,-1],[-1,0],[0,1],[1,0]] # 移动数组，[r, c] 分别表示行移动和列移动向量，并且位置i与face对应，比如'L'表示左转，位置是行不变。列负方向移动一位\n",
    "\n",
    "        x,y,p = 0,0,2 # 初始位置和face\n",
    "        path[(x,y)] = '_' # 初始路径\n",
    "\n",
    "        for i in range(K):\n",
    "            if (x,y) in path and path[(x,y)] == 'X': # （x,y）是走过的点，且之前的值是‘X’\n",
    "                path[(x,y)] = '_' # 按题意转换颜色\n",
    "                p = (p-1)%4 # 按题意，需要逆时针旋转，即face数组反着移动一位\n",
    "\n",
    "            else: # (x,y)没走过，或者之前的值是‘_’\n",
    "                path[(x,y)] = 'X' # 按题意转换颜色\n",
    "                p = (p+1)%4 # 按题意，需要顺时针旋转，即face数组正向着移动一位\n",
    "                        \n",
    "            x,y = x + move[p][0], y + move[p][1] # 根据朝向，移动到新的位置上\n",
    "\n",
    "            # 记录边界\n",
    "            min_x = min(min_x, x)\n",
    "            min_y = min(min_y, y)\n",
    "            max_x = max(max_x, x)\n",
    "            max_y = max(max_y, y)\n",
    "\n",
    "        # 根据边界，初始化矩阵\n",
    "        board = [['_' for _ in range(max_y-min_y+1)] for _ in range(max_x-min_x+1)]\n",
    "\n",
    "        for (i,j), mark in path.items():\n",
    "            board[i-min_x][j-min_y] = mark # 把（min_x, min_y）设置为坐标零点，进行坐标变化并设置矩阵格里面的值\n",
    "\n",
    "        board[x-min_x][y-min_y] = face[p] # x,y 是最终的位置，坐标变换后，设置蚂蚁的朝向\n",
    "\n",
    "        res = [''.join(row) for row in board]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "directions = [(1, 0), (0, -1), (-1, 0), (0, 1)]\n",
    "idx = ['R', 'D', 'L', 'U']\n",
    "class Solution:\n",
    "    def move(self, place, d, dic):#给当前坐标 翻转 判断 移动   \n",
    "        if dic[tuple(place)] == 1:\n",
    "            dic[tuple(place)] = 0\n",
    "            d += 1\n",
    "            #print('顺时针')\n",
    "        else:#if dic[tuple(place)] == 0:\n",
    "            dic[tuple(place)] = 1\n",
    "            d -= 1\n",
    "           # print('逆时针')\n",
    "        nextplace = [place[0] + directions[d % 4][0], place[1]+ directions[d % 4][1]]\n",
    "        if tuple(nextplace) not in dic.keys():\n",
    "            dic[tuple(nextplace)] = 1\n",
    "            #print('nextplace init')\n",
    "        return nextplace, d, dic#返回下一步的坐标， 方向，以及记录的字典\n",
    "\n",
    "    def printKMoves(self, K):\n",
    "        dic = {}\n",
    "        place = [0, 0]\n",
    "        direction = 0\n",
    "        dic[tuple(place)] = 1\n",
    "        for _ in range(K):\n",
    "            place , direction, dic= self.move(place, direction, dic)\n",
    "        max0 = -1000000\n",
    "        min0 = 1000000\n",
    "        max1 = -1000000\n",
    "        min1 = 1000000\n",
    "        for k in dic.keys():\n",
    "            if k[0] > max0:\n",
    "                max0 = k[0]\n",
    "            if k[0] < min0:\n",
    "                min0 = k[0]\n",
    "            if k[1] > max1:\n",
    "                max1 = k[1]\n",
    "            if k[1] < min1:\n",
    "                min1 = k[1]\n",
    "        yist = abs(min1 - max1) + 1\n",
    "        xist = abs(min0 - max0) + 1\n",
    "        res = [['_' for _ in range(xist)] for _ in range(yist)]\n",
    "\n",
    "        for X_Y, v in dic.items():\n",
    "            #print(X_Y, v)\n",
    "            x = X_Y[1] - min1\n",
    "            y = X_Y[0] - min0\n",
    "            if v == 0:\n",
    "                res[x][y] = 'X'\n",
    "            if (place[0], place[1]) == (X_Y[0], X_Y[1]):\n",
    "                res[x][y] = idx[direction % 4]\n",
    "        res.reverse()\n",
    "        res = [''.join(c for c in res[i]) for i in range(yist)]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        res = []\n",
    "        dir = [\"R\", \"D\", \"L\", \"U\"]\n",
    "        move = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        self.curDir = 0\n",
    "        r = 0\n",
    "        c = 0\n",
    "        data = {}\n",
    "        minR = 0\n",
    "        minC = 0\n",
    "        maxR = 0\n",
    "        maxC = 0\n",
    "        def fill(r, c, offset, color):\n",
    "            data[(r, c)] = color\n",
    "            self.curDir += offset\n",
    "            if self.curDir < 0:\n",
    "                self.curDir = 3\n",
    "            elif self.curDir > 3:\n",
    "                self.curDir = 0\n",
    "            r += move[self.curDir][0]\n",
    "            c += move[self.curDir][1]\n",
    "            return r, c\n",
    "\n",
    "        while K:\n",
    "            \n",
    "            if (r, c) not in data:\n",
    "                r, c = fill(r, c, 1, \"X\")\n",
    "            else:\n",
    "                if data[(r, c)] == \"_\":\n",
    "                    r, c = fill(r, c, 1, \"X\")\n",
    "\n",
    "                elif data[(r, c)] == \"X\":\n",
    "                    r, c = fill(r, c, -1, \"_\")\n",
    "            print(r, c)\n",
    "            minC = min(minC, c)\n",
    "            minR = min(minR, r)\n",
    "            maxC = max(maxC, c)\n",
    "            maxR = max(maxR, r)\n",
    "            K -= 1\n",
    "        height = maxR + abs(minR) + 1\n",
    "        width = maxC + abs(minC) + 1\n",
    "        data[(r, c)] = dir[self.curDir]\n",
    "        #print(data)\n",
    "        for i in range(height):\n",
    "            res.append([\"_\" for _ in range(width)])\n",
    "        #print(res)\n",
    "        for (r, c) in data:\n",
    "            color = data[(r, c)]\n",
    "            r += abs(minR)\n",
    "            c += abs(minC)\n",
    "            res[r][c] = color\n",
    "        final_res = []\n",
    "        for d in res:\n",
    "            final_res.append(\"\".join(d))\n",
    "        return final_res\n",
    "       # _U  X_\n",
    "       # X_  XU\n",
    "       # XX  __"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        d = [(0,1,'R'),(1,0,'D'),(0,-1,'L'),(-1,0,'U')]\n",
    "        x, y = 2000, 2000\n",
    "        mnx, mxx, mny, mxy = x, x, y, y\n",
    "        t = [[0] * 3000 for _ in range(3000)]\n",
    "        color = ['_', 'X']\n",
    "        p = 0\n",
    "        \n",
    "        for _ in range(K):\n",
    "            if t[x][y]:\n",
    "                p = (p + 3) % 4\n",
    "            else:\n",
    "                p = (p + 1) % 4\n",
    "            t[x][y] ^= 1\n",
    "            x += d[p][0]\n",
    "            y += d[p][1]\n",
    "            mnx, mxx, mny, mxy = min(mnx, x), max(mxx, x), min(mny, y), max(mxy, y)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(mnx, mxx + 1):\n",
    "            tmp = ''\n",
    "            for j in range(mny, mxy + 1):\n",
    "                if i == x and j == y:\n",
    "                    tmp += d[p][2]\n",
    "                else:\n",
    "                    tmp += color[t[i][j]]\n",
    "            ans.append(tmp)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        if(K == 0):\n",
    "            return [\"R\"]\n",
    "        minD,minU,minL,minR = 2500,2500,2500,2500\n",
    "        grid = [['_']*5000 for _ in range(5000)]\n",
    "        curX,curY = 2500,2500\n",
    "        curOreient = 'R'\n",
    "        while(K):\n",
    "            if(grid[curX][curY] == '_'):\n",
    "                grid[curX][curY] = 'X'\n",
    "                if(curOreient == 'R'):\n",
    "                    curOreient = 'D'\n",
    "                    curY-=1\n",
    "                    minD = min(minD,curY)\n",
    "                elif(curOreient == 'L'):\n",
    "                    curOreient = 'U'\n",
    "                    curY+=1\n",
    "                    minU = max(minU,curY)\n",
    "                elif(curOreient == 'U'):\n",
    "                    curOreient = 'R'\n",
    "                    curX+=1\n",
    "                    minR = max(minR,curX)\n",
    "                else:\n",
    "                    curOreient = 'L'\n",
    "                    curX-=1\n",
    "                    minL = min(minL,curX)\n",
    "            else:\n",
    "                grid[curX][curY] = '_'\n",
    "                if(curOreient == 'R'):\n",
    "                    curOreient = 'U'\n",
    "                    curY+=1\n",
    "                    minU = max(minU,curY)\n",
    "                elif(curOreient == 'L'):\n",
    "                    curOreient = 'D'\n",
    "                    curY-=1\n",
    "                    minD = min(minD,curY)\n",
    "                elif(curOreient == 'U'):\n",
    "                    curOreient = 'L'\n",
    "                    curX-=1\n",
    "                    minL = min(minL,curX)\n",
    "                else:\n",
    "                    curOreient = 'R'\n",
    "                    curX+=1\n",
    "                    minR = max(minR,curX)\n",
    "            K-=1\n",
    "        res = []\n",
    "        for i in range(minU,minD-1,-1):\n",
    "            s = ''\n",
    "            for j in range(minL,minR+1):\n",
    "                if(i == curY and j == curX):\n",
    "                    s+=curOreient\n",
    "                else:\n",
    "                    s+=grid[j][i]\n",
    "            res.append(s)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        if K == 0:\n",
    "            return ['R']\n",
    "        direc_dict = {'R':('D', 'U'),\n",
    "        'D':('L', 'R'),\n",
    "        'L':('U', 'D'),\n",
    "        'U':('R','L')}\n",
    "        mat = [[True]*int(K**0.75+4) for _ in range(int(K**0.75+4))]  # T白 F黑\n",
    "        x, y = len(mat)//2, len(mat)//2\n",
    "\n",
    "        # 设定边界\n",
    "        ul, dl, ll, rl = x, x, y, y\n",
    "        k = 0\n",
    "        direction = 'R'\n",
    "        while k < K:\n",
    "            if mat[x][y]:\n",
    "                mat[x][y] = False\n",
    "                direction = direc_dict[direction][0]\n",
    "                if direction == 'R':\n",
    "                    y += 1\n",
    "                    rl = max(rl, y)\n",
    "                elif direction == 'D':\n",
    "                    x -= 1\n",
    "                    dl = min(dl, x)\n",
    "                elif direction == 'L':\n",
    "                    y -= 1\n",
    "                    ll = min(ll, y)\n",
    "                elif direction == 'U':\n",
    "                    x += 1\n",
    "                    ul = max(ul, x)\n",
    "            else:\n",
    "                mat[x][y] = True\n",
    "                direction = direc_dict[direction][1]\n",
    "                if direction == 'R':\n",
    "                    y += 1\n",
    "                    rl = max(rl, y)\n",
    "                elif direction == 'D':\n",
    "                    x -= 1\n",
    "                    dl = min(dl, x)\n",
    "                elif direction == 'L':\n",
    "                    y -= 1\n",
    "                    ll = min(ll, y)\n",
    "                elif direction == 'U':\n",
    "                    x += 1\n",
    "                    ul = max(ul, x)\n",
    "            k += 1\n",
    "        \n",
    "        ans = []\n",
    "        for row in range(ul, dl-1, -1):\n",
    "            row_tmp = []\n",
    "            for col in range(ll, rl+1):\n",
    "                if mat[row][col]:\n",
    "                    row_tmp.append('_')\n",
    "                else:\n",
    "                    row_tmp.append('X')\n",
    "            ans.append(row_tmp)\n",
    "        ans[ul-x][y-ll] = direction\n",
    "        \n",
    "        ans = [''.join(row) for row in ans]\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def printKMoves(self, K: int) -> List[str]:\n",
    "        if K == 0:\n",
    "            return ['R']\n",
    "        direc_dict = {'R':('D', 'U'),\n",
    "        'D':('L', 'R'),\n",
    "        'L':('U', 'D'),\n",
    "        'U':('R','L')}\n",
    "        mat = [[True]*int(K**0.75+4) for _ in range(int(K**0.75+4))]  # T白 F黑\n",
    "        x, y = len(mat)//2, len(mat)//2\n",
    "\n",
    "        # 设定边界\n",
    "        ul, dl, ll, rl = x, x, y, y\n",
    "        k = 0\n",
    "        direction = 'R'\n",
    "        while k < K:\n",
    "            if mat[x][y]:\n",
    "                mat[x][y] = False\n",
    "                direction = direc_dict[direction][0]\n",
    "                if direction == 'R':\n",
    "                    y += 1\n",
    "                    rl = max(rl, y)\n",
    "                elif direction == 'D':\n",
    "                    x -= 1\n",
    "                    dl = min(dl, x)\n",
    "                elif direction == 'L':\n",
    "                    y -= 1\n",
    "                    ll = min(ll, y)\n",
    "                elif direction == 'U':\n",
    "                    x += 1\n",
    "                    ul = max(ul, x)\n",
    "            else:\n",
    "                mat[x][y] = True\n",
    "                direction = direc_dict[direction][1]\n",
    "                if direction == 'R':\n",
    "                    y += 1\n",
    "                    rl = max(rl, y)\n",
    "                elif direction == 'D':\n",
    "                    x -= 1\n",
    "                    dl = min(dl, x)\n",
    "                elif direction == 'L':\n",
    "                    y -= 1\n",
    "                    ll = min(ll, y)\n",
    "                elif direction == 'U':\n",
    "                    x += 1\n",
    "                    ul = max(ul, x)\n",
    "            k += 1\n",
    "        \n",
    "        ans = []\n",
    "        for row in range(ul, dl-1, -1):\n",
    "            row_tmp = []\n",
    "            for col in range(ll, rl+1):\n",
    "                if mat[row][col]:\n",
    "                    row_tmp.append('_')\n",
    "                else:\n",
    "                    row_tmp.append('X')\n",
    "            ans.append(row_tmp)\n",
    "        ans[ul-x][y-ll] = direction\n",
    "        \n",
    "        ans = [''.join(row) for row in ans]\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
